﻿#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct NumberComparator
{
    bool operator()(const int& a, const int& b)
    {
        return a > b;
    }
};

// 利用小根堆
static int splitCost(const int* numbers, size_t count)
{
    priority_queue<int, vector<int>, NumberComparator> heap;
    for (int i = 0; i < count; i++)
    {
        heap.push(numbers[i]);
    }

    int total = 0;
    while (heap.size() > 1)
    {
        int sum = heap.top();
        printf("%d ", sum);
        heap.pop();
        sum += heap.top();
        printf("%d ", heap.top());
        heap.pop();
        total += sum;
        heap.push(sum);
        printf("\n");
    }

    return total;
}

//  一块金条切成两半，是需要花费和长度数值一样的铜板的。比如长度为20的金条，不管切成长度多大的两半，都要花费20 个//铜板。
// 一群人想整分整块金条，怎么分最省铜板？
// 例如，给定数组[10, 20, 30], 代表一共三个人，整块金条长度为10 + 20 + 30 = 60. 
// 金条要分成10, 20, 30三个部分。如果先把长度60的金条分成10和50，花费60；
// 再把长度50的金条分成20和30，花费50；一共花费110铜板。
// 但是如果先把长度60的金条分成30和30，花费60；再把长度30金条分成10和20，花费30；一共花费90铜板。 
// 输入一个数组，返回分割的最小代价。
int main_LessMoneySplitGold()
{
    int numbers[] = { 10,20,30,40,50 };
    int count = sizeof(numbers) / sizeof(int);
    int cost = splitCost(numbers, count);
    printf("%d\n", cost);

    return 0;
}